The RSA Factoring Challenge was a challenge put forward by

RSA Laboratories RSA Security LLC, formerly RSA Security, Inc. and doing business as RSA, is an American computer and network security company with a focus on encryption and encryption standards. RSA was named after the initials of its co-founders, Ron Rivest, ...

on March 18, 1991 to encourage research into

computational number theory In mathematics and computer science, computational number theory, also known as algorithmic number theory, is the study of computational methods for investigating and solving problems in number theory and arithmetic geometry, including algorithm ...

and the practical difficulty of factoring large

integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...

s and cracking RSA keys used in

cryptography Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...

. They published a list of

semiprime In mathematics, a semiprime is a natural number that is the product of exactly two prime numbers. The two primes in the product may equal each other, so the semiprimes include the squares of prime numbers. Because there are infinitely many prime nu ...

s (numbers with exactly two

prime factor A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...

s) known as the

RSA numbers In mathematics, the RSA numbers are a set of large semiprimes (numbers with exactly two prime factors) that were part of the RSA Factoring Challenge. The challenge was to find the prime factors of each number. It was created by RSA Laboratories i ...

, with a cash prize for the successful factorization of some of them. The smallest of them, a 100-decimal digit number called RSA-100 was factored by April 1, 1991. Many of the bigger numbers have still not been factored and are expected to remain unfactored for quite some time, however advances in

quantum computer Quantum computing is a type of computation whose operations can harness the phenomena of quantum mechanics, such as superposition, interference, and entanglement. Devices that perform quantum computations are known as quantum computers. Though ...

s make this prediction uncertain due to

Shor's algorithm Shor's algorithm is a quantum algorithm, quantum computer algorithm for finding the prime factors of an integer. It was developed in 1994 by the American mathematician Peter Shor. On a quantum computer, to factor an integer N , Shor's algorithm ...

. In 2001, RSA Laboratories expanded the factoring challenge and offered prizes ranging from $10,000 to $200,000 for factoring numbers from 576 bits up to 2048 bits. The RSA Factoring Challenges ended in 2007. RSA Laboratories stated: "Now that the industry has a considerably more advanced understanding of the cryptanalytic strength of common symmetric-key and public-key algorithms, these challenges are no longer active." When the challenge ended in 2007, only RSA-576 and RSA-640 had been factored from the 2001 challenge numbers. The factoring challenge was intended to track the cutting edge in integer factorization. A primary application is for choosing the

key length In cryptography, key size, key length, or key space refer to the number of bits in a key used by a cryptographic algorithm (such as a cipher). Key length defines the upper-bound on an algorithm's security (i.e. a logarithmic measure of the faste ...

of the RSA

public-key encryption Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic alg ...

scheme. Progress in this challenge should give an insight into which

key size In cryptography, key size, key length, or key space refer to the number of bits in a key used by a cryptographic algorithm (such as a cipher). Key length defines the upper-bound on an algorithm's security (i.e. a logarithmic measure of the faste ...

s are still safe and for how long. As RSA Laboratories is a provider of RSA-based products, the challenge was used by them as an incentive for the academic community to attack the core of their solutions — in order to prove its strength. The RSA numbers were generated on a computer with no network connection of any kind. The computer's hard drive was subsequently destroyed so that no record would exist, anywhere, of the solution to the factoring challenge. The first RSA numbers generated, RSA-100 to RSA-500 and RSA-617, were labeled according to their number of

decimal The decimal numeral system (also called the base-ten positional numeral system and denary or decanary) is the standard system for denoting integer and non-integer numbers. It is the extension to non-integer numbers of the Hindu–Arabic numeral ...

digits; the other RSA numbers (beginning with RSA-576) were generated later and labelled according to their number of

binary Binary may refer to: Science and technology Mathematics * Binary number, a representation of numbers using only two digits (0 and 1) * Binary function, a function that takes two arguments * Binary operation, a mathematical operation that ta ...

digits. The numbers in the table below are listed in increasing order despite this shift from decimal to binary.

The mathematics

RSA Laboratories states that: for each RSA number ''n'', there exists

prime number A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...

s ''p'' and ''q'' such that :''n'' = ''p'' × ''q''. The problem is to find these two primes, given only ''n''.

The prizes and records

The following table gives an overview over all RSA numbers. Note that the RSA Factoring Challenge ended in 2007 and no further prizes will be awarded for factoring the higher numbers. :''The challenge numbers in white lines are part of the original challenge and are expressed in

base 10 The decimal numeral system (also called the base-ten positional numeral system and denary or decanary) is the standard system for denoting integer and non-integer numbers. It is the extension to non-integer numbers of the Hindu–Arabic numer ...

, while the challenge numbers in yellow lines are part of the 2001 expansion and are expressed in base 2''

Notes

{{DEFAULTSORT:Rsa Factoring Challenge Integer factorization algorithms Cryptography contests 1991 establishments in the United States

The mathematics

The prizes and records

See also

Notes